package arr

/*
通过高斯定理求出原本不缺少数字情况下的总和-缺少数字情况下的总和
时间复杂度：O(N)
空间复杂度:O(1)
*/
func missingNumber(arr []int) int {
	sum := 0
	n := len(arr)
	for _, v := range arr {
		sum += v
	}
	return (arr[0]+arr[n-1])*(n+1)/2 - sum
}

/*
先求出公差d，然后如果arr[i]+d不等于arr[i+1]，则缺少数字为arr[i]+d
时间复杂度：O(N)
空间复杂度:O(1)
*/
func missingNumber1(arr []int) int {
	// 先求出公差
	n := len(arr)
	d := (arr[n-1] - arr[0]) / n
	var i = 0
	for ; i < n-1; i++ {
		if arr[i]+d != arr[i+1] {
			break
		}
	}
	return arr[i] + d
}
